Two Sum

两个解法

• 排序后从两端逼近 Onlogn & Ologn
• 一遍扫描，用哈希表存储已扫数 On & On

快排解法

struct Num{
    i: usize,
    v: i32
}

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        use std::convert::TryInto;

        let mut nums  = nums.iter().enumerate().map(|(i, v)| {
            Num{i: i.clone(), v: v.clone()}
        }).collect::<Vec<_>>();

        nums.sort_by(|a, b| {
            a.v.cmp(&b.v)
        });
        let mut l = 0;
        let mut r = nums.len() - 1;

        while l < r {
            let res = nums[l].v + nums[r].v - target;
            if res == 0 {
                return vec![nums[l].i.try_into().unwrap(), nums[r].i.try_into().unwrap()];
            } else if res > 0 {
                r = r - 1;
            } else if res < 0 {
                l = l + 1;
            }
        }
        unreachable!();
    }
}